TEXT ANALYSIS

BDA_5_1

Text Data Access

Obiettivo del text data access è connettere gli utenti con le giuste informazioni al momento giusto.

• text data access è un processo che permette di trovare le informazioni contenute in un testo.

• la connessione utente - informazione può essere fatta in due modi:

  • pull: l'utente cerca di estrarre le informazioni dal sistema, ad esempio tramite una query di keywords.

  • push: il sistema di raccomandazione cerca di fornire le informazioni all'utente, anche senza che quest'ultimo le abbia richieste.

    

Text retrieval

• La connessione tra utente e informazione è mediata solitamente da un text retrieval system(serch engine)

• è un sistema che permette di trovare i documenti che contengono le informazioni cercate dall'utente.

• I motori di ricerca sono usati per fornire raccomandazioni o navigazione.

• il text retrieval dal punto di vista dell'utente:

  • consiste nell'utilizzare una query per trovare documenti rilevanti in una collezione di documenti testuali.

• text retrival è un sottotask dell'information retrieval, che è il processo di trovare informazioni (non solo testuali, video , immagini etc...) rilevanti per un utente da una collezione di informazioni.

• Il text retrieval dipende dalle query:

• Una query di solito è piuttosto breve e incompleta (non è un linguaggio formale come SQL).

  • può essere una domanda, una frase o una lista di parole chiave.

• Il bisogno di informazione può essere difficile da descrivere precisamente, specialmente quando l'utente non è familiare con l'argomento.

• Ciò che conta come risposta corretta è soggettivo

• I motori di ricerca sono interrogati con:

  • query di navigazione: l'utente vuole trovare un documento specifico o un insieme di documenti.
  • query informative: l'utente vuole trovare informazioni su un argomento.

C'è una grande dofferenza fra le query usate per fare text retrieval su un search engine e quelle usate per interrogare un database.

Text Retrieval vs Database Retrieval

• Struttura dei dati nei Database:

  • i dati sono strutturati e ogni campo ha un significato definito secondo uno schema.

• Struttura dei dati nei motori di ricerca:

  • i dati sono non strutturati e non c'è nessuno schema che definisce il significato dei campi.

• Query nei Database:

  • Le query dei database specificano i vincoli sui campi della tabella dei dati

• Query nei motori di ricerca:

  • sono basate su parole chiave e rappresentano solo una specifica vaga dei documenti desiderati.

I risultati attesi:

• nei database si possono ottenere elementi di dati specifici;
• nel text retrieval si ottiene un insieme di documenti rilevanti.

Le sfide sono diverse:

nei database:

• non c'è la sfida di determinare quali elementi di dati soddisfano la query dell'utente e quindi dovrebbero essere restituiti
• la sfida è quella di restituire i risultati in modo efficiente.

nei motori di ricerca:

• la sfida è stabilire quali documenti restituire per una query prima di preoccuparsi di restituire le risposte in modo rapido.
• la valutazione di quale risposta sia migliore dipende dall'utente.
• Non esiste un modo matematico per dimostrare che una risposta sia migliore di un'altra;
• si deve sempre fare affidamento su valutazioni empiriche utilizzando test e utenti.

Document selection vs Document Ranking

Strategie per il text retrieval nei search engines

• Il text retrieval può essere fatto tramite due approcci:

  • 1) document selection:
  • 2) document ranking:

• sia $ V = \{ w_1, w_2, ..., w_n\} $ l'insieme di tutti i termini di un vocabolario di un linguaggio naturale.

• $ w_i $ è una parola.

• sia la query $ q = \{q_1, q_2, ..., q_m\} $ una serie di parole usate per descrivere il contesto di ricerca.

• $ q_i \in V $ è una keyword della query.

• sia un documento $ D_i = \{d_{i1}, d_{i2}, ..., d_{ik}\} $ una sequenza di parole.

• $ d_{ij} \in V $ .

• la query $ q $ è sempre più corta di un documento $ D_i $.

• $ |q| < |D_i| $.

• sia $ C = \{D_1, D_2, ..., D_n\} $ una collezione di documenti.

Obiettivo:

• Ottenere un sottoinsieme $ R(q) \subseteq C $ di tutti i documenti che soddisfano la query $ q $.

• Realmente si ottiene $R'(q) $ in quanto non si conoscono tutti i documenti rilevanti e quindi tutto $ R(q) $.

  • quindi $R'(q)$ un'approssimazione di $ R(q) $.

  • $ R'(q) $ si ottiene con le due strategie:

  • document selection

  • document ranking

document selection

• si implementa un classificatore binario $f(q,d)$ che classifica in:

• relevant: $f(q,d) = 1$ se $d \in R(q)$

• non relevant: $f(q,d) = 0$ se $d \notin R(q)$

• in base alla query $q$.

• $R'(q)$ è l'insieme di tutti i documenti classificati come relevant.

  • $R'(q) = \{d \in C | f(q,d) = 1\}$

  • si stima la rilevanza assoluta di un documento $d$ per la query $q$.

• ogni documento deve essere confrontato con tutti i documenti della collezione per stabilire l'ordine di rilevanza.

document ranking

• questa strategia ordina i documenti in base alla loro rilevanza per la query $q$.

• si implementa una funzione di ranking $f(q,d) \in \mathbb{R}$ che:

  • assegna un punteggio a ogni documento $d$ in base alla query $q$

• si ordinano i documenti in base al punteggio(ranking) in modo decrescente.

• Il set $R(q)$ è parzialmente deciso dal sistema di ranking e parzialmente dall'utente.

• l'utente può implicitamente scegliere una soglia $\theta$ e considerare solo i documenti con un punteggio maggiore di $\theta$.

• $R'(q)= \{d |f(q,d) \geq \theta\}$

• non è necessario confrontare ogni documento con tutti i documenti della collezione.

• viene stimata la rilevanza relativa dei documenti e si ordina la collezione in base a se la funzione di ranking di un certo documento è maggiore di quella di un altro

  • ogni documento viene confrontato con un numero limitato di documenti della collezione.

Il Ranking è generalmente preferito perchè la stima della rilevanza relativa è più facile della stima della rilevanza assoluta.

• implementare un classificatore binario è più difficile che implementare una funzione di ranking.

  • difficile di trovare un criterio per classificare la rilevanza di un documento.

    • il classificatore molto probabilmente non sarà accurato.

probability ranking principle:

• Ottenere una lista di documenti ordinato in maniera decrescente in base al rank è dimostrato essere la strategia migliore per il text retrieval se:

1.  l'utente visualizza i documenti in maniera sequenziale 

2.  la rilevanza di un documento è indipendente dalla rilevanza di altri documenti.

Retrieval Models

Per implementare un search engine è necessario oltre a una strategia di ranking anche un modello che permetta di definire la rilevanza formalmente così da poterla misurare.

Ci sono due famiglie di modelli di retrieval.

La rilevanza di un documento viene calcolata in maniera differente basandosi su due approcci:

• 1 similarità (Similarity retrieval models)

• 2 probabilità (Probability retrieval models).

Similarity retrieval models

• la funzione di ranking di un documento è calcolata in base a una misura di similarità tra la query e il documento.

• Vector Space Model fa parte di questa famiglia.

  • la distanza è calcolata in base alla similarità tra i vettori che rappresentano la query e il documento.

Probability retrieval models

• la funzione di ranking di un documento è calcolata in base alla probabilità che il documento sia rilevante per la query.

• la query e il documento sono visti come osservazioni di due variabili aleatorie.

• Una variabile aleatoria binaria $R$ che indica se un documento è rilevante o meno per una query.

• il ranking del documento è la probabilità che $R(q, d) = 1$.

• esempi di modelli di retrieval probabilistici sono:

  • Classic probabilistic model:

    • assumono che la probabilità di rilevanza di un documento sia indipendente dalla probabilità di rilevanza di altri documenti.

  • Language model:

    • basati sulla query likelihood che è la probabilità che la query sia generata dal documento.

  • Divergence from randomness model:

    • basati sulla divergenza tra la distribuzione di probabilità della query e la distribuzione di probabilità del documento.

Molti Retrieval models rappresentano il testo di un documento usando un bag of words.

• a ogni parola è associato uno score che indica la sua importanza nel documento.

• lo score può essere rispetto a:

  • 1: frequenza della parola nel documento.

  • 2: frequenza della parola nella collezione.

  • 3: lunghezza del documento

• Queste tre misure cercano di caratterizzare la popolarità del termine nella raccolta e sono combinate per ottenere lo score finale.

  • con una funzione si determina il contributo complessivo della corrispondenza di una parola, con una correzione per la lunghezza del documento.

  • La corrispondenza con un termine raro contribuisce maggiormente al punteggio complessivo rispetto alla corrispondenza con un termine comune.

es: data la frase "presidential campaign news",

• $q = \{presidential, campaign, news\}$

• Lo funzione di ranking di una query rispetto a un documento è basata sulla combinazione degli score delle parole che compongono la query.

Vector Space Retrieval Model

• è un modello di retrieval basato sulla similarità tra la query e il documento

• la query e il documento sono rappresentati come vettori di termini.

• i vettori possono essere una parola, una frase o un n-gramma di parole.

• Se abbiamo un vocabolario di $|V|$ termini(vettori), stiamo definendo uno spazio vettoriale di dimensione $|V|$.

• Ogni parola del vocabolario è una base ortogonale dello spazio vettoriale. (sono gli assi dello spazio vettoriale)

• la similarità è calcolata in base alla distanza tra i vettori che rappresentano la query e il documento.

• i termini del vettore query rappresenta i pesi con cui vengono combinati i termini del vettore documento.

• funzione di similarità più semplice è il prodotto scalare tra i vettori.

• oppure uso Similarità del coseno

esempio di vector space model tri-dimensionale (vocabolario con 3 parole):

• programming;
• library;
• presidenzial;

• In termini di rappresentazione del documento trascuriamo informazioni come:

  • l'ordine delle parole

  • la struttura sintattica

  • la struttura semantica

• è considerato un modello di retrieval semplificato.

Come rapppresentare le query e i documenti nello spazio vettoriale

Dobbiamo assegnare dei pesi ai termini che rappresentano le componenti dei vettori query e documento.

Dato una vocabolario:

• $V = \{w_1, w_2, w_3, ..., w_{|V|}\}$ $ = \{news, about, presidential, campaign, food,...\}$

• il vettore di termini di una query $q$ è un vettore binario di dimensione $|V|$.

• ogni valore dei vettori $q, d$ se è 1 indica la presenza di una parola di $q$ o $d$ nel vocabolario.

  • $q_1 = 1$ se la parola $w_1\in V$ (es: 'news') è presente nella query $q$.

- avrà come valore 1 se il termine è nel vocabolario, 0 altrimenti.

ES: Si implementa un vector space model per calcolare la rilevanza tra la query $q$ e la collezione $D = \{d_1, d_2, d_3, d_4, d_5\}$

simplest vector space model

• $f(q, d_i) = q \cdot d_i = \sum_{i=1}^{|V|} x_i \cdot y_i$

• è la funzione di similarità tra la query $q$ e il documento $d_i$.

• ci sono dei problemi usando questo semplice modello:

• d2 è rilevante come d4

• in d4 appare due volte la parola 'presidential' e d2 una sola volta.

• d4 dovrebbe essere più rilevante di d2.

• Data una query e dei un documenti si usa la frequenza del termine per rappresentare i pesi dei termini.

  • $TF(w)$ numero di volte che appare il termine $w$

• $ q= (x_1, x_2, ..., x_{|V|})$

  • $x_i = TF(w_i, q)$
  • conteggio della parola $w_i$ nella query $q$.

• $ d= (y_1, y_2, ..., y_{|V|})$

  • $y_i = TF(w_i, d)$
  • conteggio della parola $w_i$ nel documento $d$.

• $Sim(q, d) = q \cdot d = \sum_{i=1}^{|V|} x_i \cdot y_i$

• = $\sum_{i=1}^{|V|} TF(w_i, q) \cdot TF(w_i, d)$

• d4 è più rilevante di d2.
• si può notare che d2 è ancora rilevante come d3.
• Intuitivamente però d3 matcha meglio la query di d2.

• 'about' non è un termine rilevante per la query come 'presidential' e 'campaign'.

• Introduciamo la Inverse Document Frequency

• 'about' è un termine molto comune nella collezione.

• 'presidential' e 'campaign' sono termini più rari e quindi più rilevanti.

• Si va a pesare la term frequency con la loro inverse document frequency.

• $IDF(w) = \frac{M+1}{df(w)}$

  • $M$: numero di documenti nella collezione.

  • $df(w)$ è la document frequency:

    • numero di documenti che contengono il termine $w$.

    

  • Penalizza i termini che sono molto frequenti nei documenti della collezione.

  • Rende più rilevanti i termini rari
    • es: 'presidential' è più raro di 'about' e quindi più rilevante.

per $q$ e $d$ avremo:

• $x_i = TF(w_i, q)$,

  • conteggio della parola $w_i$ nella query $q$.
  • $y_i = TF(w_i, d) \cdot IDF(w_i)$,
    • conteggio della parola $w_i$ nel documento $d$ pesato dalla sua frequenza inversa nei documenti della collezione.

• usando la IDF nel conteggio dei termini nel documento si ottiene un punteggio più alto per i documenti che contengono termini rari nella collezione di documenti.

• problema:

  • se un documento ha un termine raro, ma è ridondante per la query, il documento avrà un punteggio alto.

es:

• per evitare questo dobbiamo rimodulare i pesi dati dalla Term Frequency (TF) = $c(w, d)$.

TERM FREQUENCY TRANSFORMATION

• $TF(w, d) = log(1 + c(w, d))$ se $c(w, d) > 0$ altrimenti 0.

oppure

• $TF(w, d) = 1 + log(1 + c(w, d)$ se $c(w, d) > 0$ altrimenti 0.

• il logaritmo è usato per evitare che i termini più frequenti abbiano un peso troppo alto.

  • log smorza il peso dei termini più frequenti.

• le parole con term frequency più alta vanno ad impattare meno sul calcolo della similarità.

• BM25 è un altra trasformazione dei pesi dati dalla Term Frequency

• $TF(w, d) = \frac{(k + 1) \cdot c(w, d)}{k +c (w, d)}$

  • $k$ è un parametro che può essere calcolato in base alla lunghezza media dei documenti della collezione.
  • è una funzione limitata superiormente da 1.
• al crescere di k la $TF(w, d) \rightarrow c(w, d)$

Altre trasformazioni della Term Frequency note in letteratura (non da sapere):

Zipf's Law: Distribuzone della frequenza delle parole

• ci sono poche parole che compaiono molto frequentemente e molte parole che compaiono raramente.

• Zipf's Law: la frequenza di una parola è inversamente proporzionale al suo rank.

  • $f_i \propto \frac{1}{r} $

  • $\rightarrow r\times f =k$

Probabilistic Retrieval Model

• La funzione di rank è basata sulla probabilità che un documento sia rilevante per una query.

• $P(R = 1 | q, d)$

  • $R$ è la variabile aleatoria che indica se il documento $d$ è rilevante per la query $q$.

  • $q$ e $d$ sono modellati come osservazioni della variabile aleatoria $R$.

    

  • nella reltà non si ha una tabella con le rilevanze di tutte le possibili combinazioni di $q$ e $d$.

    Problema:

  • Come assegnare R = 1 o R = 0 a $q$ e $d$?
  • non si osservano tutte le possibili combinazioni di $q$ e $d$.

• Assunzione:

  • assumiamo che un utente formuli una query basandosi su una rilevanza immaginaria $R$ per il documento $d$.

• Possiamo calcolare la probabilità che dato un documento che l'utente reputa interessante, $d$ venga ottenuto come risultato di una query $q$.

• Si usa quindi l'approssimazione:

• $P(R = 1 | q, d) \approx P(q |d, R = 1)$

• $P(q |d, R = 1)$:

  -probabilità che la query $q$ sia generata da un utente che reputa il documento $d$ rilevante.

  • d con R=1 significa che all'utente interessa il documento d.

• $P(R = 1 | d)$:

  • probabilità che il documento $d$ sia rilevante per la query $q$.

Query likelihood Retrieval Model

• data una query $q = w_1, w_2, ..., w_n$

  • Si assume che le parole della query siano statisticamente indipendenti tra loro.

  • $P(q |d) = P(w_1|d) \cdot P(w_2|d) \cdot ... \cdot P(w_n|d)$

    • probabilità che la query $q$ sia generata da un utente che reputa il documento $d$ rilevante.

    • $P(w_i|d)$: probabilità che la parola $w_i$ sia generata dal documento $d$.

  • nel log space:

  • $log P(q |d) = log P(w_1|d) + log P(w_2|d) + ... + log P(w_n|d)$

• ipotesi:

  • d è un documento ideale che soddisfa la query q fatta dall'utente

  • le parole della query sono generate da una distribuzione di probabilità $P(w | d)$

    • ie le parole della query sono campionate dal documento $d$.

• un modello fatto cosi è soggetto a questo problema:

  • se una query contiene una parola che non è nel documento, la probabilità che la query sia generata dal documento è 0.

• Realisticamente:

  • l'utente non usa necessariamente parole del documento per fare le query.

Soluzione:

• Assunzione:

  • l'utente non ha in mente un documento ideale, ma genera una distribuzione di parole non necessariamente contenute nel documento.

• Serve un modello che non assegni probabilità 0 a query che contengono parole che non sono nel documento (unseen words).

Stima della probabilità $P(w | d)$ considerando le unseen words:

• Questa stima si calcola tramite un lenaguage model.

• Un language model fornisce una distribuzione di probabilità su una sequenza di parole.

• Usando la Maximum Likelihood Estimation (MLE): (nel grafico sotto in nero)

  • $P(w | d) = \frac{c(w, d)}{|d|}$

  • $c(w, d)$: numero di occorrenze della parola $w$ nel documento $d$.

  • $|d|$: lunghezza del documento $d$.

• le parole che non sono nel documento hanno probabilità 0.

• Si usa uno smoothed language model per evitare che le parole che non sono nel documento abbiano probabilità 0

  • (nel grafico sotto in rosso)

• viene modellata $P(w | C)$ come probabilità che la parola $w$ sia generata da una collezione di documenti $C$.

• le parole che non sono nel documento vengono modellate con probabilità proporzionale alla loro distribuzione nella collezione.

• Query likelihood retrieval formula (Ranking function with smoothing):

• per implementare il modello bisogna sapere come stimare $P(w | C)$

• capire come settare il parametro $\alpha_d$

  • regola la lunghezza di normalizzazione del documento.

LANGUAGE MODELS

• Si vuole assegnare una probabilità ad una frase o ad una parola

• UN modello che calcola la probabilità di una frase o di una parola è un Language Model.

• $P(W) = P(w_1, w_2, ..., w_n)$ o $P(w_n\ |\ w_1, w_2, ..., w_{n-1})$

  • $w_i$ è una parola.

  • $W$ è una frase.

• Possibili utilizzi dei Language Models:

Unsmoothed N-gram Language Model

Si calcola la probabilità di una parola w data la sequenza di parole che la precedono h:

• $P(w\ |\ h) = \frac{count(h, w)}{count(h)}$

• h = “its water is so transparent that”

• w = “the”

• Questo sistema è utile per i sistemi di correzione ortografica o di completamento automatico.

• ma se la frase completa è poco frequente, la probabilità sarà vicina a 0.

• ci sono troppi documenti possibili, quindi la probabilità di una frase completa è molto bassa.

• frasi simili che differiscono per un sinonimo hanno probabilità molto diverse.

N-gram Language Models

Ricordando che:

• $ P(w_1, w_2, ..., w_n) = $

$ P(w_1)\cdot P(w_2\ |\ w_1)\cdot P(w_3\ |\ w_1, w_2)\cdot ... \cdot P(w_n\ |\ w_1, w_2, ..., w_{n-1}) $

$ = \prod_{i=1}^{n} P(w_i\ |\ w_1, w_2, ..., w_{i-1})$

Invece di calcolare la probabilià della prossima parola date tutte le parole precedenti, si calcola la probabilità della prossima parola data le ultime $n-1$ parole.

$ P(w_{1},\ldots ,w_{m})\approx \prod _{i=2}^{m}P(w_{i}\mid w_{i-(n-1)},\ldots ,w_{i-1})$

per chiarire se n = 3 and i = 5: (avremo un trigramma)

$ P(w_{i}\mid w_{i-(n-1)},\ldots ,w_{i-1})= P(w_{5}\mid w_{3},w_{4})$

BIGRAMMA

• $P(w_i\ | \ w_{i-1})$ , data la parola precedente, calcola la probabilità della parola corrente.

• si può estendere a trigrammi, 4-grammi, ecc. per questo si parla di N-gramma.

• Di solito è un modello insufficente, perchè non tiene conto del contesto, ovvero delle dipendenze delle parole lontane.

MLE per stimare la probabilità di un n-gramma

• MLE è la Maximum Likelihood Estimation.

• Dato un bigramma:

  • la probabilità di una parola data la parola precedente si stima come:

  • $P_{MLE}(w_i\ |\ w_{i-1}) = \frac{count(w_{i-1}, w_i)}{count(w_{i-1})}$

    • $count(w_{i-1}, w_i)$: numero di volte che la parola $w_i$ segue la parola $w_{i-1}$.

    • $count(w_{i-1})$: numero di volte che la parola $w_{i-1}$ appare nel corpus.

• esempio, dato un corpus di 3 frasi:

MLE N-grams

• sia $w^{i-1} = w_1, w_2, ..., w_{i-1}$ una sequenza di parole, allora:

• sia $w^{i-1}_{i-(n-1)} = w_{i-(n-1)},..., w_{i-1}$ una sequenza di parole troncata, allora:

• $P_{MLE}(w_i\ |\ w^{i-1}_{i-(n-1)}) = \frac{count(w^{i-1}_{i-(n-1)}, w_i)}{count(w^{i-1}_{i-(n-1)})}$

• $count(w^{i-1}_{i-(n-1)}, w_i)$:

  • numero di volte che la parola $w_i$ segue la sequenza di parole troncata $w^{i-1}_{i-(n-1)}$.

• $count(w^{i-1}_{i-(n-1)})$:

  • numero di volte che la sequenza di parole troncata $w^{i-1}_{i-(n-1)}$ appare nel corpus.

esempio di bigram models

• suppenendo che dal modello bigramma si ottengano le seguenti probabilità:

  • $P(I|<s>) = 0.25$
  • $P(want|I) = 0.33$
  • $P(english|want) = 0.0011$
  • $P(food|english) = 0.5$
  • $P(</s>|food) = 0.68$

se vogliamo calcolare la probabilità della frase:

$(<s>$ I want english food $</s>)$

$P(</s>$ I want english food $</s>) = $

$$= P(I|<s>) \times P(want|I) \times P(english|want) \times P(food|english) \times P(</s>|food) = $$$$ = 0.25 × 0.33 × 0.0011 × 0.5 × 0.68 = 0.000031 $$$$\prod_{i=1}^{n} P(w_i\ |\ w_1, w_2, ..., w_{i-1}) \rightarrow 0$$

• Per evitare l'underflow si lavora nello spazio logaritmico:

$$log(P1 \times P2 \times P3 \times P4 \times P5) = log(P1) + log(P2) + log(P3) + log(P4) + log(P5)$$

Overfitting nell'N-gram Language Model

• N-gram stima delle buone probabilità solo se il corpus di test è simile al corpus di training.

• nella pratica, il corpus di training è sempre troppo piccolo per coprire tutte le possibili frasi.

• se nel corpus di train non c'è una frase $w^{n-1}$

  • $P(w_n \ |\ w^{n-1}) = 0$

• serve una tecnica per stimare la probabilità di una frase che non è presente nel corpus di training.

Laplace Smoothing

• aggiungo 1 a tutti i conteggi.

  • così non avrò n-gramm con probabilità 0.

• $P_{Laplace}(w_i\ |\ w^{i-1}_{i-(n-1)}) = \frac{count(w^{i-1}_{i-(n-1)}, w_i) + 1}{count(w^{i-1}_{i-(n-1)}) + |V|}$

  • $|V|$: numero di parole nel vocabolario.

Il laplace smoothing è una approssimazione della probabilità reale. In verità va a modificare la distribuzione di probabilità degli n-grammi.

vediamo un esempio di costruzione di bigrammi su un certo corpus di testo:

• conto ogni volta che una parola segue un'altra parola.

• calcolo la probabilità di ogni bigramma.

  • $P_{laplace}(w_i\ |\ w_{i-1}) = \frac{count(w_{i-1}, w_i) + 1}{count(w_{i-1}) + |V|}$

• invertendo il processo:

• ritorno dalla probabilità al conteggio con la formula:

  $ count^*(w_{i-1}, w_i) = [count(w_{i-1}, w_i) + 1] \times \frac{count(w_{i-1})}{count(w_{i-1}) + |V|}$

Search Engine Implementation

Un search engine è un informazione retrieval system che permette di trovare informazioni fra un insieme di dati di vario tipo, fra cui testi, immagini, video, ecc.

• Abbiamo parlato in particolare del 'text retrieval':

  • strategie di retrieval;

    • document selection;
    • document ranking;

  • retrieval models;

    • similarity-based;
    • probabilistic;

  • language models;

    • n-gram language models;
    • smoothing;
    • MLE;
    • Laplace smoothing;

• Un informazione retrieval system è composto da 4 componenti:

Tokenizer:

• è il primo step di ogni task di text mining.

• divide il testo in token (parole, simboli, ecc.).

  • scelta delle regole di tokenizzazione
    • es. trattamento delle parole composte, trattamento dei numeri, apostrofi, ecc.

• determina come rappresentare i documenti.

  • ogni documento è rappresentato da un vettore di token, ognuno con un indice univoco.
  • ogni token è un vettore di feature.
  • ci sono diverse strtegie di feature generation:
  • bag of words;
  • Term Frequency (TF);
  • n-grams;
  • word embeddings;

Indexer:

• Serve per permettere ad un search engine di poter indicizzare moli di dati più grandi di quanto possano essere caricati nella memoria del sistema.

• è inefficiente fare lo scan di tutto il corpus per ogni query.

• Un sistema di indexing carica una porzione del corpus in memoria

• crea un indice che permette di trovare rapidamente i documenti che contengono un certo token.

• Viene usata una struttura dati chiamata inverted index:

  • per ogni documento viene salvata la lista dei token che contiene e associato un Document ID.

  • si crea una tabella che raggruppa tutti i token estratti dai documenti ordinati per Document ID.

• si ordinano i token in ordine alfabetico

• si contano i token uguali con stesso Document ID

• vengono raggruppati i token uguali con stesso Document ID

• si aggiunge alla tabella una colonna con la document frequency (DF) del token

• il file viene quindi diviso in:

  • dictionary:

    • contiene tutti i termini da tenere in memoria.
    • devono essere sempre accessibili.

  • postings file:

    • contiene Document Id, DF e posizione del token nel documento.
    • Salvato su disco.

• per la legge di Zipf, le parole più comuni appaiono molte volte nei documenti;

• con questa struttura dati si risparmia spazio di memoria
  • non si salvano i token duplicati delle parole comuni dei documenti.

Scorer/Ranker

• Funzione che Permette al Retrieval System di assegnare uno score a ogni documento per ogni query in modo efficiente

  • si può fare con un inverted index.

    • fornisce le informazioni necessarie per calcolare lo score di ogni documento per ogni query.

      esempio di Ranker: Scorer term at a time Ranking

      

Feedback

• Si aggiunge un ulteriore step al retrieval system per migliorare la qualità dei risultati.

• Si aggiungono informazioni sulle query per migliorare la qualità dei risultati.

  • Le informazioni possono essere:

    • esplicite:
      • l'utente può dire se i risultati sono rilevanti o meno.

    • implicite:

      • tutte le informazioni che si possono ricavare dall'interazione dell'utente con il sistema.

      • es. tempo speso su una pagina, click, scroll, ecc.

    • non è detto che le informazioni implicite siano utili per migliorare i risultati della query.

• Diversi tipi di feedback:

Relevance Feedback:

• l'utente può dire quali risultati sono rilevanti o meno.

• tali risultati sono usati dal sistema per la Query Expansion

• se l'utente dice che un documento è rilevante, si può usare il contenuto del documento per espandere la query.

• si aggiungono i termini più frequenti del documento alla query.

• ci permette di imparare cosa è interessante per l'utente.

Pseudo-Relevance feedback**

• si usano i primi k risultati della query come feedback.

• questi k risultati sono usati come query expansion.

• non sempre è possibile avere feedback espliciti dall'utente.

• è possibile avere feedback impliciti dall'utente.

  • es. tempo speso su una pagina, click, scroll, ecc.

Implicit Feedback

• Si basa sui dati raccolti nell'interazione fra l'utente e il sistema.

  • es:
    • tempo speso su una documenti;
    • click;
    • scroll;
    • ecc.

Feedback in Vector Space Model

• Il VSM fornisce la rilevanza di un documento per una query.

• Si vuole usare il feedback per espandere la query (la query viene modificta in base al feedback).

  • è come mappare la query in uno spazio a dimensione maggiore, dove la query è più simile ai documenti rilevanti.

Rocchio Feedback:

• é il sistema di feedback basato su VSM.

• tramite la funzione di similarità si calcola la distanza fra la query e i documenti.

• si individuano i documenti più simili alla query.

  • documenti top ranked (+)

• si calcola il centroide dei documenti top ranked.

• si calcola il centroide dei documenti non rilevanti.

• geometricamente:

  • si sposta il vettore $q$
    • verso il centroide dei documenti rilevanti;
    • lontano dal centroide dei documenti non rilevanti.

• il vettore query risultante sarà:

• $ q_m = \alpha q_0 + \beta \frac{1}{|D_r|} \sum_{d \in D_r} d - \gamma \frac{1}{|D_{nr}|} \sum_{d \in D_{nr}} d $

  • $q_0$ è la query originale.
  • $D_r$ è l'insieme dei documenti rilevanti.
  • $D_{nr}$ è l'insieme dei documenti non rilevanti.
  • $\alpha, \beta, \gamma$ sono parametri che determinano l'importanza dei termini della query originale, dei termini dei documenti rilevanti e dei termini dei documenti non rilevanti, per la nuova query espansa.

• i termini dei documenti rilevanti avranno un peso maggiore dei termini dei documenti non rilevanti nel mofiicare la query originale.

Esempio:

• potenziali problemi:

  • costo computazionale elevato

    • si devono calcolare i centroidi dei documenti rilevanti e non rilevanti.
    • si aggiornano i pesi dei termini della query.

  • considerando solo i documenti rilevanti avremo pochi termini per espandere la query.

  • la media dei documenti non rilevanti può aver contenuto informativo utile per espandere la query.

• overfitting:

  • per evitare l'overfitting

  • abbiamo bisogno di un numero sufficiente di documenti rilevanti per espandere la query.

  • è importante tenere conto della query originale.

    • non è detto che la query originale sia necessario espanderla
      • ie è già abbastanza specifica.

Text Classification

La classificazione dei testi è il processo di assegnazione di categorie di soggetti, argomenti o generi a un dato documento.

Può essere utilizzata per:

• il rilevamento dello spam,
• l'identificazione della paternità,
• l'identificazione dell'età e del genere,
• l'identificazione della lingua
• Sentiment analysis

I metodi di classificazione:

• Supervised Machine Learning

  • prevede un insieme fisso di classi e un insieme di documenti etichettati per l'addestramento,

Input:

• a document d
• a fixed set of classes C = {c1, c2,..., cJ}
  • dati etichettati a mano per assegnare etichette di senso alle parole nel contesto.
• A training set of m hand-labeled documents (d1,c1),....,(dm,cm)

Output:

• a learned classifier f: D -> C

• classifictori:

  • Naive Bayes
  • Support Vector Machines
  • Decision Trees
  • Neural Networks
  • etc ...

Computational Lexical Semantics

• si riferisce a qualsiasi processo computazionale che coinvolge il significato delle parole.

• Comprende compiti quali

• il calcolo della somiglianza tra parole,
• il calcolo delle relazioni tra parole,
• la disambiguazione del senso delle parole e l'etichettatura dei ruoli semantici.

Relazioni tra parole

Lemma: è la forma base di una parola.

• es. "running" è la forma base di "run", "runs", "ran", "runner", ecc.

Relazioni tassonomiche

For example, "car" is a hyponym of "vehicle"

• Le relazioni tassonomiche si riferiscono all'organizzazione gerarchica delle parole in categorie.

• Le relazioni tra parole o sensi possono essere classificate in diverse categorie:

  • sinonimi
  • antonimi
  • iponimi
  • ipernimi

• I sinonimi sono parole che hanno lo stesso o quasi identico significato,

• Gli antonimi sono parole con significato opposto.

• Gli iponimi sono parole più specifiche di un'altra parola

• Gli ipernimi sono parole più generali.

• Anche la parentela e la somiglianza tra parole sono concetti importanti per comprendere le relazioni tra le parole.

• La semantica vettoriale e la disambiguazione del senso delle parole sono due metodi utilizzati per rappresentare e distinguere i diversi significati delle parole.

Come dare significato alle parole

• Dictionary-based approach

  • ci si basa su dizionari lessicali per definire il significato delle parole.

• Vector-semantics approach

  • si mappano le parole in vettori di numeri reali, in cui le parole con significati simili hanno vettori simili (vicini fra loro).

Dictionary-based approach

I dizionari contengono definizioni di parole:

• serve definire relazioni tra parole

• sono contenuti su appositi database.

• non è facile da estendere ad altre lingue.

• andrebbe aggiornato continuamente per star dietro all'evoluzione della lingua.

• per risolvere problemi come la circolarità delle definizioni

  • es. "a car is a vehicle"

• si usa la semantica lessicale, che studia il significato delle parole e le loro relazioni, come i sinonimi e i contrari.

• Anche il contesto in cui le parole si trovano può fornire indizi sul loro significato

  • le parole che si trovano in contesti simili tendono ad avere significati simili.

• es. WordNet

• WordNet è un dizionario lessicale per l'inglese.

• la semantica lessicale studia il significato delle parole e le loro relazioni, come i sinonimi e i contrari.
• associa parole con significati e relazioni semantiche.

Word sense disambiguation

• i metodi basati su dictionary neccessitano di un processo di disambiguazione del senso delle parole (Word sense disambiguation, WSD)

• si vuole determinare il significato corretto di una parola nel contesto, dato un inventario fisso di potenziali sensi della parola.

• es.

• "I went to the bank to deposit my money"

• "The bank of the river was covered with dead fish"

• utilizzata in diverse applicazioni,

• come:

  • la traduzione automatica,
  • la risposta alle domande
  • la sintesi vocale.

tecniche di Word sense Disambiguation

• Supervised Machine Learning
• Thesaurus/Dictionary Methods

Supervised Word Sense Disambiguation

utilizza un insieme di dati etichettati in base al loro 'significato' per addestrare un classificatore che predirrà la classe(significato) di una parola in un determinato contesto.

Estrazione delle caratteristiche:

• Collocational features

  • le parole vicine alla parola target sono le features per il classificatore.
  • le parole vicine rappresentano il contesto della parola target.
  • Si tiene conto solo della parola specifica che compare in una certa posizione, senza considerare il contesto più ampio.

• Bag of words features

  • non considera la posizione delle parole vicine rispetto alla parola target.

  • prende un set di parole nello stesso corpus della parola target e le utilizza come caratteristiche per il classificatore.

  • può tenere conto della:

    • frequenza delle parole
    • presenza/assenza delle parole
    • lunghezza del testo in cui la parola target appare

Dictionary and Thesaurus classification methods

• Il thesaurus o tesauro è il lessico dei termini relativi a un ambito generale o specifico di conoscenze, collegati tra loro in una rete gerarchica e relazionale.

I Thesaurus methods sono un'alternativa agli algoritmi supervisionati per la disambiguazione del senso quando i dati di addestramento etichettati sono limitati e costosi.

• Questi metodi utilizzano dizionari e tesauri o basi di conoscenza simili per una supervisione indiretta.

  • il contesto di una parola viene confrontato con le definizioni delle parole nel dizionario o nel thesaurus per determinare il senso corretto della parola.

• sono detti a supervisione debole

  • non utilizzano testi etichettati a mano per evidenziare una relazione semantica tra le parole.

Lesk Algorithm semplificato

es: disambiguazione di 'bank' con WordNet

• attribuiamo significato a 'bank' in base alle altre parole che compaiono nella frase.

• nella frasse troviamo parole usate per definire bank $^1$

• bank $^1$ sarà il significato di 'bank' nella frase.

L'algoritmo di Lesk

• a cosa serve:
  • disambiguare il senso delle parole basata su dizionari
• come funziona nella pratica:
  • la parola target viene confrontata con le definizioni delle parole nel dizionario o nel thesaurus per determinare il senso corretto della parola.
  • non viene usata solo la definizine della parola target.

Algoritmo basato su dizionari per la disambiguazione di senso:

• sceglie il senso la definizione del dizionario condivide il maggior numero di parole con la parola target.

• Lesk semplificato sembra funzionare meglio di altri di quello originale.

Vector-semantics approach

• le tecniche di word disambiguation basate sui dizionari sono limitate dalla disponibilità di dizionari e dalla loro copertura.

• Si passa da una semantica lessicale a una semantica vettoriale, che rappresenta le parole come vettori numerici n-dimensionali.

• La semantica vettoriale è basata sull'ipotesi distribuzionale, che afferma che il significato di una parola è determinato dal suo contesto.

Vector semantics and word embeddings

• il processo di rappresentazione delle parole come vettori è chiamato word embedding.

• Si modella il significato delle parole embeddandole in uno spazio vettoriale.

• le parole sono rappresentate da vettori di dimensione fissa.

• Le parole nello stesso contesto tendono ad avere significati simili.

  • saranno rappresentate da vettori simili.

• I vector semantic models possono essere appresi automaticamente dal testo senza alcuna etichettatura o supervisione complessa

• mentre in molte applicazioni di linguistica computazionale il significato delle parole è rappresentato da un indice di vocabolario o "numero di parole".

Vector Semantic Models

• I modelli di semantica vettoriale possono fornire una rapprentazione sparsa o densa delle parole.

• Rappresentazione vettoriali sparse

  • vettori grandi e con molti zeri

  • Matrici di co-occorrenza basate su:

    1. conteggio delle occorrenze dei termini nei documenti
    2. co-occorrenza dei termini con il contesto (altre parole)
    3. term frequency-inverse document frequency (TF-IDF)
    4. Pointwise Mutual Information (PMI)

• Rappresentazione vettoriali dense

• vettori piccoli e con pochi zeri

1. Algoritmi di riduzione della dimensionalità

   • Single Value Decomposition (SVD) è utilizzato per ridurre la dimensione di una matrice di parole.

     • LSA è un'applicazione di SVD per la rappresentazione vettoriale delle parole.

2. Modelli di Word Embedding basati su reti neurali (Neural language models)

• forniscono embedding statici delle parole

  • una volta che il modello è addestrato, i vettori delle parole non cambiano.

• Word2Vec

  • skip-gram
  • CBOW

1. Modelli di Word Embedding basati su reti neurali ricorrenti o trasformers

• forniscono embedding dinamici delle parole

  • la stessa parola può avere embedding diversi in base al contesto in cui appare.

- il modello è allenato per prevedere la parola successiva in base alle seqquenze di parole precedenti, che sono il contesto della parola target.

Vettori e parole

Sparse Vectore Representations with Co-occurrence Matrices

Term-document matrix

• mostra la frequenza di occorrenza di una parola in un documento

• raw are words in the vocabulary

  • n° raws = $|v|$
• columns are documents in the collection
  • n° columns = $|d|$
• valori: frequenza delle parole nei documenti

$M_{|v|\times|d|}$

• due documenti sono simili se i vettori colonna sono simili

  • $vettore_{colonna} \in \mathbb{R}^{|v|}$

• due parole sono simili se i vettori riga sono simili

  • $vettore_{riga} \in \mathbb{R}^{|d|}$

Term-Term of context matrix

• rappresentazione matematica di un corpus testuale che mostra la frequenza di co-occorrenza delle parole e del loro contesto.

• le righe rappresentano le parole ;

• le colonne il contesto.

  • Il contesto può essere definito come le parole che compaiono nella stessa frase o paragrafo della parola target.

• le parole e il contesto sono i due componenti principali che vengono utilizzati per calcolare la frequenza di co-occorrenza.

• $M_{|v|\times|v|}$

  • $vettore_{riga} \in \mathbb{R}^{|v|}$
  • $vettore_{colonna} \in \mathbb{R}^{|v|}$

• $|V|$ è la dimensione del vocabolario;

• ogni parola avrà $|V|$ componenti nel vettore;

• le componenti del vettore saranno per lo più 0;

  • è infatti una rappresentazione sparsa

Misure di similarità tra vettori basati su frequenza di co-occorrenza

1. Dot Product

   • il prodotto scalare tra due vettori:

   • $v \cdot w = \sum_{i=1}^{n} v_i w_i$

   • tende a dare risultati più alti quando i vettori hanno valori alti nelle stesse dimensioni.

   • favorisce in generale i vettori con pochi zeri e valori alti.

   • favorisce quindi le parole più frequenti.

   • non è una buona misura di similarità tra parole.

2. Cosine Similarity

• a partire dal dot product si può calcolare la cosine similarity tra due vettori:

  $a \cdot b = ||a|| \cdot ||b|| \cdot cos(\theta)$

  $cos(\theta) = \frac{a \cdot b}{||a|| \cdot ||b||}$

• la similarità coseno tra due vettori:

  $cos(v,w) = \frac{v \cdot w}{||v|| \cdot ||w||}$ $= \frac{\sum_{i=1}^{n} v_i w_i}{\sqrt{\sum_{i=1}^{n} v_i^2} \sqrt{\sum_{i=1}^{n} w_i^2}}$

  

• le frequenze di co-occorrenza sono non negativi, quindi la cosine similarity per i vettori della matrice termine-termine varia da 0 a 1.

es:

• Le matrici di co-occorrenza sono spesso molto grandi e sparse.

• La term frequency può essere utile per avere info sul contesto di una parola.

• non è abbastanza perchè le parole comuni hanno frequenze elevate e non sono utili per la disambiguazione del senso.

• la soluzione è utilizzare: la term-frequency - inverse document frequency (tf-idf) come pesi dei vettori.

Term-frequency - inverse document frequency vector(tf-idf)

• Tf-idf come misura per la matrice di co-occorrenza delle parole.

• penalizza le parole che sono comuni in tutti i documenti.

• per la parola $t$ nel documento d:

  $w_{t, d} = TF_{t, d} \times IDF_{t}$

• frequenza della parola w nel documento d:

  $TF_{w, d} = count(w, d) $

  (approx. in log space)

  $= log(1 + count(w, d))$

• inverse document frequency della parola w:

  $ IDF_{w} = log(\frac{N}{DF_{w}})$

• $DF_{w}$ = numero di documenti che contengono la parola w

• $N$ = numero totale di documenti della collezione

Pointwise Mutual Information (PMI)

• Misura se due variabili co-ooccorrono più spesso di quanto ci si aspetterebbe appaiano indipendentemente.

• $PMI(w1, w2) = log(\frac{P(w1, w2)}{P(w1)P(w2)})$

  • $P(w1, w2)$ = probabilità che la parola w1 e la parola w2 co-occorrono
  • $P(w1)$ = probabilità che la parola w1 occorra indipendentemente da w2
  • $P(w2)$ = probabilità che la parola w2 occorra indipendentemente da w1

• quando $\frac{P(w1, w2)}{P(w1)P(w2)} < 1$ le due variabili non sono indipendenti

  • $P(w1, w2)$ è inferiore a $P(w1)P(w2)$ e quindi $PMI(w1, w2)$ è spesso negativo
    • $log(0-1) \in [-\infty, 0]$

• si sostitscono i valori negativi con 0

  • $ PMI(w1, w2) = max(0, log(\frac{P(w1, w2)}{P(w1)P(w2)}))$

es:

• Sparse versus dense vectors:

tf-idf (or PMI) vectors are

◦ long (length |V|= 20,000 to 50,000)

◦ sparse (most elements are zero)

Alternative: learn vectors which are ◦ short (length 50-1000)

◦ dense (most elements are non-zero)

• vettori densi permettono di generalizzare meglio
  • catturanano meglio le relazioni tra le parole

Dense Vector Representations with SVD

Singular Value Decomposition

• La Decomposizione ai Valori Singolari (SVD) è un metodo che permette di riurre la dimensionalità di una matrice in un numero minore di dimensioni. Ciò viene fatto attraverso una rotazione degli assi in direzione della maggior varianza dei dati. In altre parole, la SVD trova le dimensioni più importanti di un dataset, cioè quelle lungo le quali i dati variano di più.

• Oss:

• la SVD si basa sulla fattorizzazione di una matrice in 3 matrici

• Si può pensare alla SVD come ad una generalizzazione della PCA, in quanto la PCA è un caso particolare della SVD.

![image.png](attachment:image.png)

Definizione

• Sia $A$ una matrice $m \times n$. A può essere scomposta, fattorizzata, in 3 matrici: $$A = U \Sigma V^T $$

dove:

• $A$ è la matrice di dati di input, di dimensioni $m \times n$
• $U$ matrice dei vettori singolari sinistri, di dimensioni $m \times m$
• $Σ$ è la matrice diagonale $m \times n$ dei valori singolari
• $V$ matrice dei vettori singolari destri, di dimensioni $n \times n$

• i vettori singolari sinistri e destri sono ortogonali tra loro

  • $U^TU = I$ e $V^TV = I$

$$ U \Sigma V^T = \sum_{i=1}^{n} \sigma_i^2 u_i v_i^T$$

• $\sigma_i$ sono valori scalari, detti valori singolari

• i vettori singolari sinistri $u_i$ sono vettori di dimensione $m$

• i vettori singolari destri $v_i$ sono vettori di dimensione $n$

SVD and term-context matrix

• L'SVD può essere applicata alla matrice termine-contesto, che rappresenta le frequenze di ogni parola in un contesto specifico.

• L'SVD suddivide questa matrice in tre matrici quadrate: una matrice di parole $W$, una matrice di valori singolari $\Sigma$ e una matrice di contesti $C$.

• Ogni riga della matrice $W$ rappresenta una parola

• le colonne rappresentano dimensioni latenti

  • i vettori colonna sono basi ortogonali dello spazio delle parole del dataset ordinate per la quantità di varianza.
  • le dimensioni a più alta varianza sono quelle che contengono più informazioni sulla parola

• La matrice $C$ è la matrice di contesti, che rappresenta le frequenze di ogni contesto in cui una parola appare.

• Ogni riga della matrice $C$ rappresenta ora le nuove dimensioni latenti

  • I vettori di riga sono ortogonali tra loro.

• le colonne rappresentano i contesti specifici.

• Oss: $W==U$

• Oss: $C==V$

Truncated SVD

• 

• utilizza solo le prime k dimensioni delle tre matrici quadrate utilizzate per suddividere la matrice termine-contesto iniziale.

• In questo modo la matrice $W$ ha dimensione $|V| \times k$,

  • e ogni riga rappresenta una parola come un vettore denso k-dimensionale (embedding).

  • la nuova matrice approssimata rappresenta l'informazione più importante della matrice originale,

    • le prime k dimensioni hanno la massima quantità di varianza nei dati.

• Oss: I valori singolari nella matrice $\Sigma$ rappresentano l'importanza relativa delle diverse dimensioni nella rappresentazione della matrice termine-contesto. I valori singolari più grandi rappresentano le dimensioni che contengono la maggior quantità di varianza nei dati e sono quindi le dimensioni più importanti per la rappresentazione della matrice termine-contesto.

• Oss: In genere, valori singolari e autovalori sono concetti distinti.

Latent Semantic Analysis (LSA)

• LSA è una tecnica usata in NLP in particolare nella semantica distributiva , per analizzare le relazioni tra un insieme di documenti e i termini che contengono producendo un insieme di concetti relativi ai documenti e ai termini.

• le parole che hanno un significato vicino ricorreranno in parti di testo simili (l' ipotesi distributiva ).

• Una matrice contenente i conteggi delle parole per documento (le righe rappresentano parole univoche e le colonne rappresentano ciascun documento)

• costruita da una grande porzione di testo

• viene utilizzata la SVD per ridurre il numero di righe preservando la struttura di somiglianza tra le colonne.

  • cosidero solo i primi k coefficienti singolari tali che:
    • $\sum_{i=1}^{k} \sigma_i \approx 0.8-0.9 $ Total Information

• I documenti vengono quindi confrontati per somiglianza del coseno tra due colonne qualsiasi. I valori vicini a 1 rappresentano documenti molto simili mentre i valori vicini a 0 rappresentano documenti molto diversi.

Word2Vec

• Si vuole predire quanto è probabile che una parola appaia in un contesto specifico.

• non si assegnano score di probabilità alle parole più probabili (classificazione multi-classe)

  • questo viene fatto con le reti neurali

• il problema di predizione delle parole viene trasformato in un problema di classificazione binaria.

  • come classificatore si usa la logistic regression

  • Invece di contare quanto spesso w1 e w2 appaiono insieme

  • si addestra un classificatore binario per predire se w2 è una parola vicina a w1 o meno.

• Si usa un approccio di apprendimento self-supervised

  • Una parola di contesto c che si trova vicino ad una parola target w nel corpus è la "risposta corretta" per l'apprendimento supervisionato.

  • Non c'è bisogno di etichette umane

• le possibili implementazioni sono due:

  • Skip-gram
  • Continuous Bag of Words (CBOW)

Skip-gram

• The skip-gram with negative sampling algorithm (skip-gram or SGNS) è un algoritmo di apprendimento self-supervised per l'apprendimento di word embeddings.

• la parola target w e le parole di contesto vicine sono visti come esempi positivi

  • $P(+|w,c)$

• si campionano casualmente alcune parole dal vocabolario per creare esempi negativi

  • $P(-|w,c) = 1 - P(+|w,c)$

• si addestra un classificatore binario(LR) basato su Logistic Regression

  • per distinguere tra esempi positivi e negativi

• la probabilità che una parola c sia vicina a una parola target w è basata sulla similarità calcolata come prodotto scalare tra i due vettori di embedding

  $$Similarity(w,c) \approx w^Tc$$

  $$P(+|w,c) = \sigma(w^Tc) = \frac{1}{1+e^{-w^Tc}}$$

  $$P(-|w,c) = 1 - \sigma(w^Tc) = \frac{1}{1+e^{w^Tc}}$$

• nello skip-gram si assume che le parole di contesto siano indipendenti tra loro

  $$P(+|w,c_1,c_2,...,c_{2m}) = \prod_{j=1}^{2m} P(+|w,c_j)$$

• in log space

  $$log P(+|w,c_1,c_2,...,c_{2m}) = \sum_{j=1}^{2m} log P(+|w,c_j)$$

• il classifcatore apprende due matrici di embedding

  • una per le parole target $W$
  • una per le parole di contesto $C$

• le matrici contengono un embedding per ogni parola nel vocabolario

• ogni parola avrà due embedding in base a se è una parola di contesto o una parola target

Apprendimento dei parametri per l'embedding

alleniamo con esempi positivi e negativi

• per ogni istanza di training (w,c)

  • creiamo k esempi negativi

• introduciamo la loss function da minimizzare per migliorare l'embedding è la log-likelihood

$$ L_{CE} = - [log P(+|w,c) + \sum_{i=1}^{k} log P(-|w,c_i)]$$

• la funzione viene ottimizata tramite discesa del gradiente

• ad ogni iterazione si aggiornano i parametri di embedding

• per la parola target w:

$$w^{t+1} = w^t - \eta \frac{\partial L_{CE}}{\partial w}$$

• per $c_+$ che per $c_-$:

$$c^{t+1} = c^t - \eta \frac{\partial L_{CE}}{\partial c}$$

• $\eta$ è il learning rate

Proprietà degli embeddings

Le parole embeddate possono essere combinate con per ottenere analogie tra i significati delle parole

• si usa la regola del parallelogramma

• problematica etica dell'embedding: